// Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.

part of dart.core;

/**
 * 列表，可索引的对象的集合。
 *
 * 本类的子类实现了不同的List。最常见的是：
 *
 * * 固定长度的List。
 *   当试图使用能更改List长度的操作时，发生错误。
 * * 可增长的List。完全实现了本类中定义的API。
 *
 * 默认的可增长List由`new List()`或`[]`返回，
 * 它维护一个内部缓冲区，并在必要的时候增大缓冲。
 * 这保证一个序列的[add]操作都会在平摊的固定时间内执行。
 * 直接设置长度可能花费与新长度成正比的时间，
 * 并且，改变内部容量会使接下来的add操作需要立即增加缓冲区容量。
 * 其它的List实现可能有不同的性能表现。
 *
 * 下面的代码说明部分List实现仅支持API的部分。
 *
 *     List<int> fixedLengthList = new List(5);
 *     fixedLengthList.length = 0;  // Error
 *     fixedLengthList.add(499);    // Error
 *     fixedLengthList[0] = 87;
 *     List<int> growableList = [1, 2];
 *     growableList.length = 0;
 *     growableList.add(499);
 *     growableList[0] = 87;
 *
 * List是[Iterable]可迭代对象，并按索引顺序进行迭代。
 * 更改值并不会影响迭代，但是会改变有效的索引&mdash;
 * 也就是改变List的长度&mdash;
 * 导致迭代步之间产生一个[ConcurrentModificationError]。
 * 这也意味着，仅可增长的List会抛出ConcurrentModificationError。
 * 如果长度暂时改变，并在继续迭代之前恢复，迭代器并不会检测到。
 *
 * 当一个操作正在List上执行时，通常情况并不允许修改List的长度（添加或删除元素）。
 * 例如，在调用[forEach]或[sort]期间。
 * 在迭代期间修改List长度，无论是直接迭代，
 * 还是通过List支持的可迭代对象迭代，都将出错。
 */
abstract class List<E> implements Iterable<E>, EfficientLength {
  /**
   * 创建一个指定长度的List。
   *
   * 如果设置了参数[length]，那么创建的List是固定长度的。
   *
   *     List fixedLengthList = new List(3);
   *     fixedLengthList.length;     // 3
   *     fixedLengthList.length = 1; // Error
   *
   * 如果未设置参数[length]，那么List的长度是0，并且是可增长的。
   *
   *     List growableList = new List();
   *     growableList.length; // 0;
   *     growableList.length = 3;
   *
   * 当使用指定长度创建一个可增长的List时，仅仅在刚创建后分配长度：
   *
   *     List growableList = new List()..length = 500;
   *
   * 如果设置参数[length]，它不能为负数或null。
   */
  external factory List([int length]);

  /**
   * 通过指定长度创建一个固定长度的List，并使用[fill]初始化每个位置的值：
   *
   *     new List<int>.filled(3, 0); // [0, 0, 0]
   *
   * [length]必须是一个非负整数。
   *
   * 如果List是可增长的，改变它的长度并不会使用[fill]来初始化新的元素。
   * 在创建和填充之后，和其它使用[List]创建的可增长或固定长度的List并没有区别。
   *
   * 返回的List中，所有的元素都是相同的[fill]值。
   * 如果指定的值是一个可变对象，那么List中所有的元素都是相同的对象，并且是可观察的。
   *
   * ```
   * var shared = new List.filled(3, []);
   * shared[0].add(499);
   * print(shared);  // => [[499], [499], [499]]
   * ```
   *
   * 你可以使用[List.generate]为List的每个位置创建一个新的对象。
   * ```
   * var unique = new List.generate(3, (_) => []);
   * unique[0].add(499);
   * print(unique); // => [[499], [], []]
   * ```
   */
  external factory List.filled(int length, E fill, {bool growable: false});

  /**
   * 创建一个包含所有[elements]的List。
   *
   * [elements]的[Iterator]规定了元素的顺序。
   *
   * 当[growable]为true（默认）时，构造函数返回一个可增长的List。
   * 否则，它返回一个固定长度的List。
   */
  external factory List.from(Iterable elements, { bool growable: true });

  /**
   * 生成一个包含所有值的List。
   *
   * 创建一个List，共[length]个元素，
   * 通过[generator]，递增的为每个`0` .. `length - 1`范围内的索引创建值。
   *
   *     new List<int>.generate(3, (int index) => index * index); // [0, 1, 4]
   *
   * 除非[growable]为true，否则创建的List是固定长度的。
   */
  factory List.generate(int length, E generator(int index),
                       { bool growable: true }) {
    List<E> result;
    if (growable) {
      result = <E>[]..length = length;
    } else {
      result = new List<E>(length);
    }
    for (int i = 0; i < length; i++) {
      result[i] = generator(i);
    }
    return result;
  }

  /**
   * 创建一个包含所有[elements]的，不可修改的List。
   *
   * [elements]的[Iterator]规定了元素的顺序。
   *
   * 不可修改的List不能改变它的长度或元素。
   * 如果元素本身是不可改变的，那么由此产生的List也是不可改变的。
   */
  external factory List.unmodifiable(Iterable elements);

  /**
   * 返回List中指定[index]位置的对象。
   * 如果[index]超出界限，将抛出[RangeError]。
   */
  E operator [](int index);

  /**
   * 使用[value]设置指定[index]位置的值。
   * 如果[index]超出界限，将抛出[RangeError]。
   */
  void operator []=(int index, E value);

  /**
   * 返回List中对象的数量。
   *
   * 对于List，有效的索引为`0`至`length - 1`。
   */
  int get length;

  /**
   * 修改List的长度。
   *
   * 如果[newLength]大于当前长度，元素将被初始化为[:null:]。
   *
   * 如果List是固定长度，则抛出[UnsupportedError]。
   */
  set length(int newLength);

  /**
   * 在List的末尾添加[value]，并扩展1个长度。
   *
   * 如果List是固定长度，则抛出[UnsupportedError]。
   */
  void add(E value);

  /**
   * 将[iterable]的所有对象附加到List的末尾。
   *
   * 通过[iterable]中对象的数量来扩展List的长度。
   * 如果List是固定长度，则抛出[UnsupportedError]。
   */
  void addAll(Iterable<E> iterable);

  /**
   * 倒序返回List中对象的[Iterable]。
   */
  Iterable<E> get reversed;

  /**
   * 按[compare]比较函数指定的顺序对List排序。
   *
   * [compare]函数必须作为一个[Comparator]。
   *
   *     List<String> numbers = ['two', 'three', 'four'];
   *     // Sort from shortest to longest.
   *     numbers.sort((a, b) => a.length.compareTo(b.length));
   *     print(numbers);  // [two, four, three]
   *
   * 如果未设置[compare]，默认List实现使用[Comparable.compare]。
   *
   *     List<int> nums = [13, 2, -11];
   *     nums.sort();
   *     print(nums);  // [-11, 2, 13]
   *
   * [Comparator]可能判断对象相等（返回0），即使它们是不同的对象。
   * 排序函数并不保证是稳定的。
   * 因此，不同的对象比较相等，在结果中仍然可能出现任何顺序。
   *
   *     List<String> numbers = ['one', 'two', 'three', 'four'];
   *     numbers.sort((a, b) => a.length.compareTo(b.length));
   *     print(numbers);  // [one, two, four, three] OR [two, one, four, three]
   */
  void sort([int compare(E a, E b)]);

  /**
   * 随机打乱List中的元素。
   */
  void shuffle([Random random]);

  /**
   * 返回List中，第一个元素[element]的索引。
   *
   * 从索引[start]处开始搜索List，一直到末尾。
   * 第一次遇到一个对象[:o:]使得[:o == element:]，则返回[:o:]的索引。
   *
   *     List<String> notes = ['do', 're', 'mi', 're'];
   *     notes.indexOf('re');    // 1
   *     notes.indexOf('re', 2); // 3
   *
   * 如果[element]未找到，返回-1。
   *
   *     notes.indexOf('fa');    // -1
   */
  int indexOf(E element, [int start = 0]);

  /**
   * 返回List中，最后一个元素[element]的索引。
   *
   * 从索引[start]开始到0，从后往前搜索List。
   * 第一次遇到一个对象[:o:]使得[:o == element:]，则返回[:o:]的索引。
   *
   *     List<String> notes = ['do', 're', 'mi', 're'];
   *     notes.lastIndexOf('re', 2); // 1
   *
   * 如果未设置[start]，那么会从List的末尾开始搜索（默认为`length-1`）。
   *
   *     notes.lastIndexOf('re');  // 3
   *
   * 如果[element]未找到，返回-1。
   *
   *     notes.lastIndexOf('fa');  // -1
   */
  int lastIndexOf(E element, [int start]);

  /**
   * 删除List中的所有对象，并且List长度变成0。
   *
   * 如果`this`是一个固定长度的List，会抛出[UnsupportedError]，并保留所有对象。
   */
  void clear();

  /**
   * 在List中的[index]位置插入对象。
   *
   * 这会增加一个List的长度，并将索引处及索引之后的所有对象，向List末尾移动。
   *
   * 如果[index]小于0或大于长度，将出错。
   * 如果List是固定长度的，将出现[UnsupportedError]。
   */
  void insert(int index, E element);

  /**
   * 在List中的[index]位置插入[iterable]的所有对象。
   *
   * 这会增加List的长度（length加上[iterable]的长度），
   * 并将所有之后的对象向List末尾移动。
   *
   * 如果[index]小于0或大于长度，将出错。
   * 如果List是固定长度的，将出现[UnsupportedError]。
   */
  void insertAll(int index, Iterable<E> iterable);

  /**
   * 从List中的[index]索引处开始，用[iterable]的所有对象重写`this`的所有对象。
   *
   *     List<String> list = ['a', 'b', 'c'];
   *     list.setAll(1, ['bee', 'sea']);
   *     list.join(', '); // 'a, bee, sea'
   *
   * 此操作并不会增加`this`的长度。
   *
   * [index]必须是非负整数，并且不大于[length]。
   *
   * [iterable]必须有足够的元素，能够从[index]开始到[length]填充元素。
   *
   * 如果`iterable`基于`this List`，它的值可能会在`setAll`操作期间改变。
   */
  void setAll(int index, Iterable<E> iterable);

  /**
   * 删除List中第一次出现的[value]。
   *
   * 如果[value]存在于List中，返回true，否则false。
   *
   *     List<String> parts = ['head', 'shoulders', 'knees', 'toes'];
   *     parts.remove('head'); // true
   *     parts.join(', ');     // 'shoulders, knees, toes'
   *
   * 如果[value]并不存在于List中，该方法不会产生影响。
   *
   *     // Note: 'head' has already been removed.
   *     parts.remove('head'); // false
   *     parts.join(', ');     // 'shoulders, knees, toes'
   *
   * 如果List是固定长度的，将出现[UnsupportedError]。
   */
  bool remove(Object value);

  /**
   * 删除List中[index]索引处的对象。
   *
   * 该方法减小了一个`this`的长度，并将所有之后对象的位置向下移了一个位置。
   *
   * 返回被删除的对象。
   *
   * [index]的取值范围必须是 `0 ≤ index < length`。
   *
   * 如果`this`是一个固定长度的List，将抛出[UnsupportedError]。
   * 在那时，List不做任何修改。
   */
  E removeAt(int index);

  /**
   * 删除（pop）并返回List的最后一个对象。
   *
   * 如果`this`是一个固定长度的List，将抛出[UnsupportedError]。
   */
  E removeLast();

  /**
   * 删除List中所有满足[test]的对象。
   *
   * 如果[:test(o):]返回true，则对象[:o:]满足[test]。
   *
   *     List<String> numbers = ['one', 'two', 'three', 'four'];
   *     numbers.removeWhere((item) => item.length == 3);
   *     numbers.join(', '); // 'three, four'
   *
   * 如果`this`是一个固定长度的List，将抛出[UnsupportedError]。
   */
  void removeWhere(bool test(E element));

  /**
   * 删除List中所有不满足[test]的对象。
   *
   * 如果[:test(o):]返回true，则对象[:o:]满足[test]。
   *
   *     List<String> numbers = ['one', 'two', 'three', 'four'];
   *     numbers.retainWhere((item) => item.length == 3);
   *     numbers.join(', '); // 'one, two'
   *
   * 如果`this`是一个固定长度的List，将抛出[UnsupportedError]。
   */
  void retainWhere(bool test(E element));

  /**
   * 返回一个新的List，包含从[start]（包括）到[end]（不包括）的对象。
   *
   *     List<String> colors = ['red', 'green', 'blue', 'orange', 'pink'];
   *     colors.sublist(1, 3); // ['green', 'blue']
   *
   * 如果未设置[end]，默认为`this`的[length]。
   *
   *     colors.sublist(1);  // ['green', 'blue', 'orange', 'pink']
   *
   * 如果[start]超出范围`0` .. `length`，
   * 或[end]超出范围`start` .. `length`，将出错。
   */
  List<E> sublist(int start, [int end]);

  /**
   * 返回一个可迭代对象[Iterable]，对[start]（包括）到[end]（不包括）的对象进行迭代。
   *
   * 如果[end]在[start]之前，将出错。
   *
   * 如果在调用方法的时候，[start]和[end]并不是有效的范围，将出错。
   * 返回的[Iterable]的行为类似`skip(start).take(end - start)`。
   * 也就是说，如果`this`改变大小，并不会抛出异常。
   *
   *     List<String> colors = ['red', 'green', 'blue', 'orange', 'pink'];
   *     Iterable<String> range = colors.getRange(1, 4);
   *     range.join(', ');  // 'green, blue, orange'
   *     colors.length = 3;
   *     range.join(', ');  // 'green, blue'
   */
  Iterable<E> getRange(int start, int end);

  /**
   * 将[iterable]中的所有元素（排除开始的[skipCount]个元素），
   * 复制到List的[start]（包括） ... [end]（不包括）范围中。
   *
   *     List<int> list1 = [1, 2, 3, 4];
   *     List<int> list2 = [5, 6, 7, 8, 9];
   *     // Copies the 4th and 5th items in list2 as the 2nd and 3rd items
   *     // of list1.
   *     list1.setRange(1, 3, list2, 3);
   *     list1.join(', '); // '1, 8, 9, 4'
   *
   * 索引[start]和[end]必须满足`0 ≤ start ≤ end ≤ length`。
   * 如果[start]等于[end]，该方法不会有任何效果。
   *
   * [iterable]跳过[skipCount]个对象后，必须有足够的对象来填充`start`到`end`的范围。
   *
   * 如果`iterable`是`this List`，
   * 操作会将原来`skipCount`到`skipCount + (end - start)`范围的元素，
   * 复制到`start`至`end`的范围，即使两个范围有重叠。
   *
   * 如果`iterable`以其它方式依赖于`this List`，结果没有任何保证。
   */
  void setRange(int start, int end, Iterable<E> iterable, [int skipCount = 0]);

  /**
   * 删除[start]（包括）到[end]（不包括）范围内的对象。
   *
   * 索引[start]和[end]必须满足范围：
   * `0 ≤ index ≤ length`，`start ≤ end`。
   *
   * 如果`this`是一个固定长度的List，将抛出[UnsupportedError]。
   * 在那时，List不做任何修改。
   */
  void removeRange(int start, int end);

  /**
   * 设置[start]（包括）到[end]（不包括）范围的对象为[fillValue]。
   *
   * 如果[start]..[end]并不是`this`一个有效的范围，将出错。
   */
  void fillRange(int start, int end, [E fillValue]);

  /**
   * 删除[start]（包括）到[end]（不包括）范围内的对象，
   * 并在它的位置插入[replacement]的内容。
   *
   *     List<int> list = [1, 2, 3, 4, 5];
   *     list.replaceRange(1, 4, [6, 7]);
   *     list.join(', '); // '1, 6, 7, 5'
   *
   * 如果[start]..[end]并不是`this`一个有效的范围，将出错。
   *
   * 该方法不会运行于固定长度的List，即使[replacement]与被替换范围的元素数量相同。
   * 在那种情况下，使用[setRange]代替。
   */
  void replaceRange(int start, int end, Iterable<E> replacement);

  /**
   * 返回一个不可修改的[Map]视图。
   *
   * Map使用List的索引作为Key值，对应的元素作为Value。
   * `Map.keys`返回的[Iterable]以数字顺序迭代`this List`的索引。
   *
   *     List<String> words = ['fee', 'fi', 'fo', 'fum'];
   *     Map<int, String> map = words.asMap();
   *     map[0] + map[1];   // 'feefi';
   *     map.keys.toList(); // [0, 1, 2, 3]
   */
  Map<int, E> asMap();
}
